Ôtômat cây

Ôtômat cây (tiếng Anh: tree automaton) là một loại máy trạng thái.[cần dẫn nguồn] Ôtômat cây xử lý cấu trúc cây, thay vì xâu như các máy trạng thái thường gặp.Bài viết này đề cập đến ôtômat phân nhánh cây, tương đương với các ngôn ngữ chính quy của cây. Một khái niệm ôtômat cây khác có thể tìm thấy là ôtômat duyệt cây. [cần dẫn nguồn]Tương tự ôtômat cổ điển, ôtômat cây hữu hạn có thể xác định (ÔHX)[cần dẫn nguồn] hoặc không (ÔHK)[cần dẫn nguồn]. Theo cách xử lý cây đầu vào, ôtômat cây hữu hạn có thể thuộc vào hai loại: (a) dưới lên, (b) trên xuống. Đây là vấn đề quan trọng vì mặc dù ôtômat ÔHK trên xuống và ÔHK dưới lên tương đương về khả năng biểu diễn nhưng ÔHX trên xuống kém hơn hẳn ôtômat dưới lên tương ứng vì tính chất của cây xác định bởi ÔHX trên xuống chỉ có thể phụ thuộc vào tính chất của đường đi. ÔHX dưới lên mạnh ngang với ÔHK.